package Demo1;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: DELL
 * Date: 2022-09-21
 * Time: 19:10
 */
public class CirculateLinkedList {
    static class ListNode {
        public int val;
        public ListNode prev;
        public ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }

    public ListNode head;//标记双向链表的头部
    public ListNode tail;//标记双向链表的尾部

    public void addFirst(int data) {

        ListNode Node = new ListNode(data);
        if (head == null) {
            head = Node;
            tail = Node;
        } else {
            Node.next = this.head;
            this.head.prev = Node;
            this.head = Node;
        }


    }

    public void addLast(int data) {
        ListNode node = new ListNode(data);
        if (this.head == null) {
            head = node;
            tail = node;
        } else {
            this.tail.next = node;
            node.prev = tail;
            this.tail = node;
        }

    }

    //任意位置插入,第一个数据节点为0号下标
    public void addIndex(int index, int data) {
        ListNode node = new ListNode(data);
        //1.判断index 是否合法
        if (index < 0 || index > size()) {
            throw new IndexIlligelException("index位置不合法！");

        }
        //2.判断特殊位置
        if (index == 0) {
            //头插法
            addFirst(data);
            return;
        }
        if (index == size()) {
            addLast(data);
            return;
        }
        //3.中间位置
        ListNode cur = findindex(index);
        //修改指向
        node.next = cur;
        cur.prev.next = node;
        node.prev = cur.prev;
        cur.prev = node;
    }

    public ListNode findindex(int index) {
        ListNode cur = this.head;
        while ((index--) != 0) {
            cur = cur.next;
        }
        return cur;
    }


    //查找是否包含关键字key是否在单链表当中
    public boolean contains(int key) {
        ListNode cur = this.head;
        while (cur != null) {
            if (cur.val == key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    //删除第一次出现关键字为key的节点
    public void remove(int key) {
        ListNode del = this.head;
        while (del != null) {
            //存在key的节点
            if (del.val == key) {
                //要删除的在头节点位置
                if (del == head) {

                    head = head.next;
                    if (head != null) {
                        //一个以上的节点
                        //只有一个节点时， head. 空指针异常
                        head.prev = null;
                    } else {
                        //一个节点
                        //tail 一直指向该节点 置空回收
                        this.tail = null;
                    }

                } else {
                    //不在头节点位置

                    //如果在头位置 del.prev. 空指针异常
                    del.prev.next = del.next;

                    //不在尾位置
                    if (del.next != null) {

                        //在尾位置 del.next. 空指针异常
                        del.next.prev = del.prev;

                    } else {
                        //在尾位置
                        // 修改tail指向
                        this.tail = del.prev;
                    }

                    //如果在尾位置 del.next. 空指针异常
                }

                return;
            } else {
                //不存在key的节点
                del = del.next;
            }

        }


        System.out.println("链表中不存在要删除的值为" + key + "的节点！");

    }

    //删除所有值为key的节点
    public void removeAllKey(int key) {
        ListNode del = this.head;
        while (del != null) {
            //存在key的节点
            if (del.val == key) {
                //要删除的在头节点位置
                if (del == head) {

                    head = head.next;
                    if (head != null) {
                        //一个以上的节点
                        //只有一个节点时， head. 空指针异常
                        head.prev = null;
                    } else {
                        //一个节点
                        //tail 一直指向该节点 置空回收
                        this.tail = null;
                    }

                } else {
                    //不在头节点位置

                    //如果在头位置 del.prev. 空指针异常
                    del.prev.next = del.next;

                    //不在尾位置
                    if (del.next != null) {

                        //在尾位置 del.next. 空指针异常
                        del.next.prev = del.prev;

                    } else {
                        //在尾位置
                        // 修改tail指向
                        this.tail = del.prev;
                    }

                    //如果在尾位置 del.next. 空指针异常
                }

            }
            //不存在key的节点
            del = del.next;
        }

    }

    //得到单链表的长度
    public int size() {

        int count = 0;
        ListNode cur = this.head;
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }

    public void display() {

        ListNode cur = this.head;
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }

    public void clear() {

        //若只置空head 和 tail 中间还有对象在引用

        //置空中间
        ListNode cur = this.head;
        while (cur != null) {
            ListNode curNext = cur.next;
            cur.next = null;
            cur.prev = null;
            cur = curNext;
        }

        //置空头尾
        head = null;
        tail = null;
    }

}


